/**
 * @author hewei
 * @version 1.0
 * @description: 周赛311 t4
 * @date 2022/9/18 10:50
 */

public class SumPrefixScores {

    public int[] sumPrefixScores(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.add(word);
        }
        int n = words.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] += trie.search(words[i]);
        }
        return ans;
    }

    class Trie {
        Trie[] next;
        int p = 0;

        public Trie() {
            next = new Trie[26];
        }

        public void add(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                int c = s.charAt(i) - 'a';
                if (node.next[c] == null) node.next[c] = new Trie();
                node = node.next[c];
                node.p++;
            }
        }

        public int search(String s) {
            Trie node = this;
            int res = 0;
            for (int i = 0; i < s.length(); i++) {
                int c = s.charAt(i) - 'a';
                if (node.next[c] == null) return res;
                node = node.next[c];
                res += node.p;
            }
            return res;
        }
    }
}
